1. Field of the Present Invention
The present invention generally relates to 3D graphics and more particularly to a system and method for bounding 3D graphic primitives to reduce the probability of failing to detect a trivial accept or trivial reject without significantly increasing the complexity of the bounding volume.
2. History of Related Art
Graphics display subsystems are almost universally encountered in microprocessor based computer systems to facilitate a variety of graphics tasks and applications. Graphics processors, graphics adapters, and a variety of similarly designed computer products provide specialized hardware to speed the execution of graphics instructions and rendering of graphic images. These processors and adapters typically include, for example, circuitry optimized for translating, rotating, and scaling 3D graphic images. In a typical application, a graphical image that is displayed on a display terminal or other output device is composed of one or more graphic primitives. For purposes of this disclosure, a graphic primitive may be thought of as one or more points, lines, or polygons that are associated with one another, such as by being connected to one another. Typically, the displayed image is generated by creating one or more graphic primitives, assigning various attributes to the graphic primitives, defining a viewing point and a viewing volume, determining which of the graphic primitives are within the defined viewing volume, and rendering those graphic primitives as they would appear from the viewing point. This process can require a tremendous amount of computing power to keep pace with the ever increasingly complex graphics applications that are commercially available. Accordingly, designers of graphics systems and graphics applications are continuously seeking cost effective means for improving the efficiency at which graphic images are rendered and displayed.
A significant portion of any graphic application is typically consumed determining what portions, if any, of a graphic primitive are within the viewing volume. If a graphic primitive is only partially within a specified viewing volume, a clipping process must be performed on the graphic primitive to eliminate the portion of the graphic primitive exterior to the viewing volume. If the graphic primitive is completely exterior to the viewing volume, further consideration of the primitive is unnecessary. If the graphic primitive is completely within the viewing volume, the rendering process may be initiated without performing any clipping. Thus, it will be appreciated by those experienced in computer graphics that determining a graphic primitive's spatial relationship to a viewing volume provides an opportunity to eliminate a potentially significant amount of processing. Unfortunately, the process of determining whether a graphic primitive is within a specified viewing volume is typically either undesirably time consuming or undesirably inaccurate. If a graphic primitive is thought of as a collection of vertices, an accurate but potentially time consuming method of determining whether the primitive is within a viewing volume includes simply determining whether each vertex of the primitive is within the viewing volume. For extremely simple graphic primitives comprised of relatively few vertices, such a direct method is preferred for its simplicity and accuracy. This direct method, however, quickly becomes burdensome as the complexity of the primitive increases. If, for example, the graphic primitive includes thousands of vertices, the direct approach will require thousand of comparisons, as each vertex is compared to the boundaries of the viewing volume using well known line clipping techniques.
The time required to complete the comparison process can be made essentially independent of the complexity of the graphic primitive if the primitive is approximated by a simple geometric shape referred to as a bounding volume that encloses the entire primitive. Regardless of the complexity of the graphic primitive that it encloses, the bounding volume is defined by a relatively few vertices. In a common application, for example, the bounding volume is the smallest rectangular parallelepiped that completely encloses the primitive. Regardless of the complexity of the primitive, this bounding volume has only eight vertices. Accordingly, a routine can quickly determine if the bounding volume is within the viewing volume by comparing just eight points to the boundaries of the viewing volume. The problem with such a simplistic bounding volume is the accuracy of the comparison results. If the graphic primitive is irregularly shaped, the simple bounding volume does a poor job of approximating the graphic primitive's shape and use of the simple bounding volume to determine whether the graphic primitive is within a viewing volume may result in a failure to detect a trivial accept or trivially reject condition. The penalty for failing to detect such trivial accept/reject conditions can be significant, especially in applications that include complex graphic primitives. Accordingly it is highly desirable to introduce a method and system for reducing the probability of failing to detect a trivial accept/reject condition without significantly impacting the performance of the trivial accept/reject process.